{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum Score of Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSumScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的最大总分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，数组长度为 <code>n</code> 。</p>\n",
    "\n",
    "<p><code>nums</code> 在下标 <code>i</code> （<code>0 &lt;= i &lt; n</code>）处的 <strong>总分</strong> 等于下面两个分数中的 <strong>最大值</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums</code><strong> 前</strong> <code>i + 1</code> 个元素的总和</li>\n",
    "\t<li><code>nums</code> <strong>后</strong> <code>n - i</code> 个元素的总和</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回数组 <code>nums</code> 在任一下标处能取得的 <strong>最大总分</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,3,-2,5]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>\n",
    "下标 0 处的最大总分是 max(4, 4 + 3 + -2 + 5) = max(4, 10) = 10 。\n",
    "下标 1 处的最大总分是 max(4 + 3, 3 + -2 + 5) = max(7, 6) = 7 。\n",
    "下标 2 处的最大总分是 max(4 + 3 + -2, -2 + 5) = max(5, 3) = 5 。\n",
    "下标 3 处的最大总分是 max(4 + 3 + -2 + 5, 5) = max(10, 5) = 10 。\n",
    "nums 可取得的最大总分是 10 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-3,-5]\n",
    "<strong>输出：</strong>-3\n",
    "<strong>解释：</strong>\n",
    "下标 0 处的最大总分是 max(-3, -3 + -5) = max(-3, -8) = -3 。\n",
    "下标 1 处的最大总分是 max(-3 + -5, -5) = max(-8, -5) = -5 。\n",
    "nums 可取得的最大总分是 -3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-score-of-array](https://leetcode.cn/problems/maximum-sum-score-of-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-score-of-array](https://leetcode.cn/problems/maximum-sum-score-of-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,-2,5]', '[-3,-5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [nums[-1]] * n \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = right[i + 1] + nums[i]\n",
    "        s = right[0]\n",
    "        ans = -inf \n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            pre += x \n",
    "            tmp = max(pre, s - pre + x)\n",
    "            if tmp > ans:\n",
    "                ans = tmp \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [nums[-1]] * n \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = right[i + 1] + nums[i]\n",
    "        s = right[0]\n",
    "        ans = -inf \n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            pre += x \n",
    "            tmp = max(pre, s - pre + x)\n",
    "            if tmp > ans:\n",
    "                ans = tmp \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        total=sum(nums)\n",
    "        s=0\n",
    "        ans=float(-inf)\n",
    "        for i,v in enumerate(nums):\n",
    "            s+=v\n",
    "            ans=max([ans,s,total+v-s])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [nums[-1]] * n \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = right[i + 1] + nums[i]\n",
    "        s = right[0]\n",
    "        ans = -inf \n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            pre += x \n",
    "            tmp = max(pre, s - pre + x)\n",
    "            if tmp > ans:\n",
    "                ans = tmp \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        ts=sum(nums)\n",
    "        s=0\n",
    "        res=-10000000000\n",
    "        for i in nums:\n",
    "            s+=i\n",
    "            ts-=i\n",
    "            res=max(res,max(s,ts+i))\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        s=sum(nums)\n",
    "        ans=-inf\n",
    "        temp=0\n",
    "        for i,k in enumerate(nums):\n",
    "            temp+=k\n",
    "            ans=max(ans,s,temp)\n",
    "            s-=k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maximumSumScore(self, nums):\n",
    "        left = nums[0]\n",
    "        right = sum(nums)\n",
    "        res = max(left, right)\n",
    "        for i in range(len(nums)-1):\n",
    "            left += nums[i+1]\n",
    "            right -= nums[i]\n",
    "            res = max(res, left, right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和\n",
    "    def maximumSumScore1(self, nums: List[int]) -> int:\n",
    "        presum, n = list(accumulate(nums, initial=0)), len(nums)\n",
    "        return max(max(presum[i + 1], presum[n] - presum[i]) for i in range(n))\n",
    "\n",
    "\n",
    "\n",
    "    # 统计和以后一边遍历一边维护答案\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        p, s, ans = 0, sum(nums), -inf\n",
    "        for num in nums:\n",
    "            ans = max(ans, max(p + num, s - p))\n",
    "            p += num\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        left, right = 0, sum(nums)\n",
    "        ans = -inf\n",
    "        for x in nums:\n",
    "            left += x\n",
    "            right -= x\n",
    "            ans = max(ans, left, right + x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "      preFix = [0]+list(accumulate(nums))\n",
    "      ans = -inf\n",
    "      for i,j in enumerate(nums):\n",
    "        ans = max(ans,max(preFix[i+1],preFix[-1]-preFix[i]))\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        presum, n = list(accumulate(nums, initial=0)), len(nums)\n",
    "        return max(max(presum[i + 1], presum[n] - presum[i]) for i in range(n))\n",
    "\n",
    "\n",
    "\n",
    "    # 统计和以后一边遍历一边维护答案\n",
    "    def maximumSumScore2(self, nums: List[int]) -> int:\n",
    "        p, s, ans = 0, sum(nums), -inf\n",
    "        for num in nums:\n",
    "            ans = max(ans, max(p + num, s - p))\n",
    "            p += num\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        presum, n = list(accumulate(nums, initial=0)), len(nums)\n",
    "        return max(max(presum[i + 1], presum[n] - presum[i]) for i in range(n))\n",
    "\n",
    "\n",
    "\n",
    "    # 统计和以后一边遍历一边维护答案\n",
    "    def maximumSumScore2(self, nums: List[int]) -> int:\n",
    "        p, s, ans = 0, sum(nums), -inf\n",
    "        for num in nums:\n",
    "            ans = max(ans, max(p + num, s - p))\n",
    "            p += num\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 前缀和\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        presum, n = [0] + list(accumulate(nums)), len(nums)\n",
    "        return max(max(presum[i + 1], presum[n] - presum[i]) for i in range(n))\n",
    "\n",
    "    # 暴力\n",
    "    def maximumSumScore2(self, nums: List[int]) -> int:\n",
    "        p, s, ans = 0, sum(nums), -inf\n",
    "        for num in nums:\n",
    "            ans = max(ans, max(p + num, s - p))\n",
    "            p += num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        presum = list(accumulate(nums))\n",
    "        res = -float(\"inf\")\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            res = max(\n",
    "                res,\n",
    "                presum[i],\n",
    "                presum[-1] - (presum[i - 1] if i > 0 else 0)\n",
    "            )\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        L=[0]*n\n",
    "        R=[0]*n\n",
    "        L[0]=nums[0]\n",
    "        R[0]=sum(nums)\n",
    "        res=-float('inf')\n",
    "        for i in range(1,n):\n",
    "            L[i]=L[i-1]+nums[i]\n",
    "            R[i]=R[i-1]-nums[i-1]\n",
    "        for i in range(n):\n",
    "            res=max(res,max(L[i],R[i]))\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
